{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "<h1><center> Network/Graph Analysis in Python </center></h1>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**NetworkX**: Python package for the creation, manipulation, and study of the structure, dynamics, and functions of complex networks.\n",
    "\n",
    "Installation: \n",
    "`$ pip install networkx`\n",
    "\n",
    "Version check in Python:\n",
    "`networkx.__version__`\n",
    "\n",
    "Upgrade:\n",
    "`$ pip install networkx --upgrade`\n",
    "\n",
    "**nxviz**: network visualization package\n",
    "\n",
    "Installation:\n",
    "`$ pip install nxviz`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import networkx as nx\n",
    "import matplotlib.pyplot as plt\n",
    "from collections import Counter\n",
    "import nxviz as nv\n",
    "\n",
    "%matplotlib inline"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Some open source network data locations:**\n",
    "\n",
    "* **graph examples embedded in NetworkX:**\n",
    "    * Zachary's Karate Club: `nx.karate_club_graph()`\n",
    "    * Davis Southern women social network: `nx.davis_southern_women_graph()`\n",
    "    *  Florentine families: `nx.florentine_families_graph()`\n",
    "    * more examples: https://networkx.github.io/documentation/networkx-1.9/examples/index.html\n",
    "* **The Koblenz Network Collection**: http://konect.uni-koblenz.de/\n",
    "* **Stanford Large Network Dataset Collection**: https://snap.stanford.edu/data/\n",
    "\n",
    "\n",
    "**To learn the basics of Network Science: http://networksciencebook.com/**\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## I. Networks Basics"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1. Create & Manipulate Networks \n",
    "\n",
    "Let's start with simple undirected and unweighted networks. An example of such networks, where we don't have edge direction (in/out) or edge weight (indicating how strong a connection is), would be the Facebook network. If you are a friend of mine, I am a friend of yours, and the edge connecting us is either 1 (connected) or non-existent (not connected). We will generate more complex networks later on."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Nodes**: can represent anything (images, webpage URL links, people, power stations, numbers, words, etc.)\n",
    "\n",
    "**Edges**: represent relationships between nodes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# create empty network (undirected graph)\n",
    "G = nx.Graph()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# add one node with label '1'\n",
    "G.add_node(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# add nodes from a list of elements\n",
    "G.add_nodes_from(['Mary', 4, 'Alice', 'Mary'])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# remove node\n",
    "G.remove_node('Mary')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# remove multiple nodes\n",
    "G.remove_nodes_from(['Mary', 1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# view nodes in network G\n",
    "G.nodes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# add single edge - tuple of nodes (source, target)\n",
    "# this also adds nodes if they don't already exist\n",
    "G.add_edge('Mary','Steven')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# add multiple of edges (list of tuples)\n",
    "G.add_edges_from([('Mary', 'Steven') , ('Mary', 'Alice')])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# view edges in network G\n",
    "G.edges"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# remove edge\n",
    "G.remove_edge('Mary','Alice')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# remove multiple edges (list of tuples)\n",
    "G.remove_edges_from([('Mary', 'Steven') , ('Mary', 'Alice')])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# get number of nodes in network G\n",
    "G.number_of_nodes()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# get number of edges in network G\n",
    "G.number_of_edges()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# get Alice's number of neighbors (connections)\n",
    "G.degree('Alice')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# empty the network\n",
    "G.clear()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Load network from file.** You can read/write a graph in a file using common graph formats (edge lists, adjacency lists, GML, GraphML, pickle, LEDA, etc.).\n",
    "\n",
    "To see how to read different types of adjancency formats, check here: https://networkx.github.io/documentation/networkx-1.10/reference/readwrite.html"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# input edgelist from file\n",
    "G = nx.read_edgelist(\"../datafiles/social/facebook/fb.txt\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# output edgelist to file\n",
    "nx.write_edgelist(G,'fb.edgelist')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# get the 2nd node's neighbors (retrieves a dictionary)\n",
    "dict_neighbors = G.neighbors('2')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "list(dict_neighbors)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# number of total nodes in graph\n",
    "len(G.nodes)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# number of total edges in graph\n",
    "len(G.edges)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.degree_assortativity_coefficient(G)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.degree_pearson_correlation_coefficient(G)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "G.clear()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2. Network Types "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### a. Weighted Graphs\n",
    "\n",
    "**Edge weight.** Consider that the edge that you are adding should contain additional information, such as the strength of the connection. This would be important, for example, when analyzing communication networks to check friendship/connectivity strength. You want to capture how many times they exchanged e-mails, calls, text messages, to indicate the strength of the connection. For this you will assign weights to the edge, values that can be the number of communications, or the fraction of communications, normalized."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# assign weight to edge\n",
    "G.add_edge('Mary','Steven', weight=5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "G.edges"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# access edge properties\n",
    "G['Mary']['Steven']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# change edge weight\n",
    "G['Mary']['Steven']['weight'] = 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### b. Directed Graphs\n",
    "\n",
    "**Edge direction.** Edges have direction describing source -> target node relationship."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#undirected\n",
    "G.nodes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "dg = nx.DiGraph()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# you can create a directed representation of network G\n",
    "dg = nx.to_directed(G)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "dg.edges"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### c. Multigraphs\n",
    "\n",
    "Many algorithms are not well defined on such graphs. Therefore, you should convert such graphs rather to a standard graph in a way that makes the measurement well defined."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# multigraphs can store multiple edges information between same two nodes that can have different properties\n",
    "MG = nx.MultiGraph()\n",
    "MG.add_weighted_edges_from([(1, 2, 3.0), (1, 2, 75), (2, 3, 5), (1, 2, 4.2)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# lists the edges (node1, node2, edge_index), including the multiedges, adding the multiedge index as 3rd element in edge tuple\n",
    "MG.edges"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# lists the edges (node1, node2, weight/edge_attribute), the 3rd element is the weights of the edges\n",
    "MG.edges.data('weight')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "MG.edges.data()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# check the weight of an edge\n",
    "MG[1][2]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### d. Bipartite Network\n",
    "\n",
    "Bipartite graphs B = (U, V, E) have two node sets U, V and edges in E that only connect nodes from opposite sets.\n",
    "\n",
    "Taken from NetworkX documentation:\n",
    "* NetworkX does not have a custom bipartite graph class \n",
    "* Graph() or DiGraph() classes can be used to represent bipartite graphs \n",
    "* you have to keep track of which set each node belongs to, and make sure that there is no edge between nodes of the same set \n",
    "* convetion: use a node attribute named *bipartite* with values 0 or 1 to identify the sets each node belongs to. This convention is not enforced in the source code of bipartite functions, it’s only a recommendation.\n",
    "\n",
    "For more details: https://networkx.github.io/documentation/stable/reference/algorithms/bipartite.html"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from networkx.algorithms import bipartite"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "bip = nx.Graph()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# add nodes with the node attribute \"bipartite\", a network of who likes what fruits\n",
    "bip.add_nodes_from(['apple', 'peach', 'watermelon', 'pear'], bipartite=0)\n",
    "bip.add_nodes_from(['Alice', 'Steve', 'Mary'], bipartite=1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "bip.add_edges_from([('Alice', 'apple'), ('Alice', 'peach'), ('Steve', 'watermelon'), \n",
    "                    ('Mary', 'pear'), ('Mary', 'apple'), ('Mary', 'watermelon')])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.draw(bip, with_labels=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "NetworkX does not provide a bipartite graph visualization method to visually delimit the two sets of nodes. However, we can draw the left and right set of nodes and see how they connect to each other. Further, you can play around with coloring the nodes based on the 'bipartite' attribute to further refine visually to which node set each node belongs to."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import scipy.sparse as sparse\n",
    "\n",
    "X, Y = bipartite.sets(bip)\n",
    "pos = dict()\n",
    "pos.update((n, (0, i*10)) for i, n in enumerate(X))\n",
    "pos.update((n, (0.5, i*10)) for i, n in enumerate(Y))\n",
    "nx.draw(bip, with_labels=True, pos=pos)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Bipartite graphs can be projected as two separate graphs G1 = (U, E1) and G2 = (V, E2). The edges will be different though. Let's take the above example. We can create a network of fruits, where nodes will be fruits and the edges will between two fruits will be created if someone likes both fruits. Such, peach and apple will have one edge, as Alice likes both. Same for apple and pear, which are both liked by Mary. Likewise, we can create the second network as the network of individuals, where connections between them will be their preference for the same fruit. Here, we can create a connection/edge between Steve and Mary since both of them like watermelon. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3. Network Models\n",
    "\n",
    "Network models can be very useful for comparing their topology to the structural properties of our network built from real data. Different network models have very distinct structural characteristics, which defines their behavior in case of information flow on the network, attacks/failures on the nodes/edges, etc, and these properties have been extensively studied and are well documented. Knowing to which network model your graph corresponds to can provide valuable insights about its potential behavior under various circumstances.\n",
    "\n",
    "There are a miriad of network models with different topological properties. Here we will try out some of the most useful ones (that frequently occur in real complex systems). \n",
    "\n",
    "For more network generation classes: https://networkx.github.io/documentation/networkx-1.10/reference/generators.html"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "# Barabasi-Albert (scale-free) network \n",
    "ba = nx.barabasi_albert_graph(50, 3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.draw_spectral(ba, node_size=5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Erdos-Renyi (random) network \n",
    "er = nx.erdos_renyi_graph(50, 0.1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.draw_circular(er)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Watts-Strogatz (small-world) network \n",
    "ws = nx.watts_strogatz_graph(50, 6, 0.2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.draw_circular(ws)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# random geometric graph (RGG)\n",
    "rgg = nx.random_geometric_graph(200, 0.125)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.draw(rgg)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# complete graph (every pair of nodes is connected by a unique edge)\n",
    "complete = nx.complete_graph(6)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.draw(complete)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## II. Analysis of Structural Properties"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 1. Node degree, network average degree, degree distribution"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "G = nx.read_gml('../datafiles/volunteer_org/org_graph.gml')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "degrees = [deg for node, deg in nx.degree(G)]\n",
    "print(degrees)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# kmin - minimum degree\n",
    "kmin = np.min(degrees)\n",
    "\n",
    "# kmax - maximum degree\n",
    "kmax = np.max(degrees)\n",
    "\n",
    "# kavg - average degree of the network\n",
    "kavg = np.mean(degrees)\n",
    "print(kmin, kmax, kavg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Degree distribution**: helps us understand connectivity trends in networks and how edges are distributed among nodes (does everyone have similar number of connections, or do we have hubs, nodes with significantly higher number of connections?)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def degree_distr(net):\n",
    "    degrees = dict(net.degree()) \n",
    "    hist = list(Counter(degrees.values()).items()) \n",
    "    hist.sort(key=lambda x:x[0])\n",
    "    hist = np.array(hist)\n",
    "    return hist\n",
    "print(degree_distr(G)) # format: [degree, num_of_nodes]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 2. Paths on Networks: average path length, shortest path, longest path"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# find shortest path between node1 and node2 in undirected networks \n",
    "nx.shortest_path(G, '0', '65')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 3. Clustering coefficient, triangles"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# triangles\n",
    "nx.triangles(G)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# clustering coefficient of a node\n",
    "nx.clustering(G, '18')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# clustering coefficient of all nodes (returns a dictionary)\n",
    "nx.clustering(G)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# clustering coefficient of the network\n",
    "cc = nx.clustering(G)\n",
    "avg_clust = sum(cc.values()) / len(cc)\n",
    "print(avg_clust)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 4. Centrality measures"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# degree centrality\n",
    "nx.degree_centrality(G)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# betweenness centrality of network\n",
    "nx.betweenness_centrality(G)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# closeness centrality of network\n",
    "nx.closeness_centrality(G)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# eigenvector centrality of network\n",
    "nx.eigenvector_centrality(G)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 5. Components"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# checks whether the network is connected\n",
    "nx.is_connected(G)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# find number of connected components\n",
    "nx.number_connected_components(G)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# get the nodes in the same component as *n*\n",
    "nx.node_connected_component(G, '0')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 6. Assortativity\n",
    "\n",
    "* Pearson correlation coefficient [-1; 1]\n",
    "* social networks are highly assortative (homophily): high degree nodes connect to other high degree nodes\n",
    "* technological are disassortative: high degree nodes connect to low degree nodes\n",
    "\n",
    "Assortativity computed based on:\n",
    "* degree\n",
    "* attribute"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.degree_assortativity_coefficient(ba)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.degree_pearson_correlation_coefficient(ba)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# check assortativity (mixing) by a particular attribute\n",
    "nx.attribute_assortativity_coefficient(ba, attribute)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## III. Network Visualization\n",
    "\n",
    "What you've all been waiting for! :)\n",
    "\n",
    "Disclaimer: visualizations can be pretty and insightful, however for large networks they tend to be just pretty! Knowing how to compute network measures is the key!\n",
    "\n",
    "* visualization with NetworkX: *\"NetworkX provides basic functionality for visualizing graphs, but its main goal is to enable graph analysis rather than perform graph visualization. In the future, graph visualization functionality may be removed from NetworkX or only available as an add-on package.\"*\n",
    "* nxviz\n",
    "* Matplotlib or Graphviz with pydot (import and export NetworkX graphs in Graphviz dot format using pydot)\n",
    "* Gephi\n",
    "* Graphviz\n",
    "* Neo4j\n",
    "* D3\n",
    "* etc."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Basic drawing methods in NetworkX module: \n",
    "* `nx.draw()`\n",
    "* `nx.random()`\n",
    "* `nx.draw_spectral()`\n",
    "* `nx.draw_circular()`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# let's create a scale-free network\n",
    "G = nx.barabasi_albert_graph(50, 3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# simplest way to draw a graph\n",
    "nx.draw(G)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# draw a graph with random layout\n",
    "nx.draw_random(G)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# draw a graph with spectral layout\n",
    "nx.draw_spectral(G)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# draw a graph with circular layout\n",
    "nx.draw_circular(G)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# nxviz package provides some nice visualization options\n",
    "import nxviz as nv"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# circle plots\n",
    "c = nv.CircosPlot(ba) \n",
    "c.draw()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# matrix plot\n",
    "nv.MatrixPlot(ba).draw()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# arc plot\n",
    "nv.ArcPlot(ba).draw()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nv.CircosPlot(rgg).draw() "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nv.CircosPlot(er).draw()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 2. Visualize subgraphs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# assign selected subgraph to a new graph\n",
    "nodes = list(ba.neighbors(10))\n",
    "nodes.append(10)\n",
    "G_sub = ba.subgraph(nodes)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# drawing options: set node size, color, labels, etc. (check documentation for more)\n",
    "nx.draw(G, node_size=30, node_color='b', with_labels=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## IV. Queries On Networks\n",
    "\n",
    "* find specific nodes\n",
    "* find specific edges"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# obtain a list of nodes with a certain property\n",
    "sub_nodes = [n[0] for n in G.nodes(data=True) if n[1]['name'].find('清华')>=0]\n",
    "print(sub_nodes)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# obtain a list of edges with a certain property\n",
    "sub_edges = [edge for edge in G.edges(data=True) if True]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# find cliques\n",
    "cli = nx.find_cliques(ba)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "list(cli)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# assign selected subgraph to a new graph\n",
    "nodes = list(ba.neighbors(10))\n",
    "nodes.append(10)\n",
    "G_sub = ba.subgraph(nodes)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# with_labels=True to show node labels\n",
    "nx.draw(G_sub, with_labels=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## V. Case Studies - Real Network Analysis from Data "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### V. 1. Social Networks - Facebook Pages\n",
    "using ***Graph Embedding with Self Clustering: Facebook data*** \n",
    "\n",
    "- data location: SNAP (Stanford Large Network Dataset Collection)\n",
    "- source: B. Rozemberczki, R. Davies, R. Sarkar and C. Sutton. GEMSEC: Graph Embedding with Self Clustering. 2018."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"../images/data.png\" alt=\"Data\" style=\"width: 300px;\"/>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* nodes: pages\n",
    "* edges: mutual likes among them -> this means undirected & networks\n",
    "\n",
    "\n",
    "There are 8 different networks representing different categories. For our current analysis, we will analyze and compare 4 networks `Company`, `Artist`, `Politician` and `Public Figure`, however, you can play with all of them to get used to manipulating networks and computing structural property measures, and to gain insights about the data."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### a. Load network from file"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# load edgelists from data file\n",
    "co_net = nx.read_edgelist(\"../datafiles/social/facebook/facebook_clean_data/company_edges.csv\", delimiter=',')\n",
    "art_net = nx.read_edgelist(\"../datafiles/social/facebook/facebook_clean_data/artist_edges.csv\", delimiter=',')\n",
    "poli_net = nx.read_edgelist(\"../datafiles/social/facebook/facebook_clean_data/politician_edges.csv\", delimiter=',')\n",
    "pub_net = nx.read_edgelist(\"../datafiles/social/facebook/facebook_clean_data/public_figure_edges.csv\", delimiter=',')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### b. Analyze network"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# check number of nodes and edges \n",
    "N = len(poli_net.nodes)\n",
    "print(N)\n",
    "\n",
    "E = len(poli_net.edges)\n",
    "print(E)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's see what is on average the number of mutual 'Likes' (connections) each page (node) has. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# calculate average degree of politician pages\n",
    "degrees = [deg for node, deg in nx.degree(poli_net)]\n",
    "kavg = np.mean(degrees)\n",
    "print(\"The # of mutual likes politician pages have on average:\", kavg)\n",
    "\n",
    "# calculate average degree of artist pages\n",
    "degrees = [deg for node, deg in nx.degree(art_net)]\n",
    "kavg = np.mean(degrees)\n",
    "print(\"The # of mutual likes artist pages have on average:\", kavg)\n",
    "\n",
    "# calculate average degree of company pages\n",
    "degrees = [deg for node, deg in nx.degree(co_net)]\n",
    "kavg = np.mean(degrees)\n",
    "print(\"The # of mutual likes company pages have on average:\", kavg)\n",
    "\n",
    "# calculate average degree of public figure pages\n",
    "degrees = [deg for node, deg in nx.degree(pub_net)]\n",
    "kavg = np.mean(degrees)\n",
    "print(\"The # of mutual likes public figure pages have on average:\", kavg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "What about the degree distribution in the networks?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "hist_poli = degree_distr(poli_net)\n",
    "hist_art = degree_distr(art_net)\n",
    "hist_co = degree_distr(co_net)\n",
    "hist_pub = degree_distr(pub_net)\n",
    "\n",
    "plt.figure()\n",
    "plt.loglog(hist_poli.T[0],hist_poli.T[1],'ro-')\n",
    "plt.loglog(hist_art.T[0],hist_art.T[1],'ko-')\n",
    "plt.loglog(hist_co.T[0],hist_co.T[1],'go-')\n",
    "plt.loglog(hist_pub.T[0],hist_pub.T[1],'bo-')\n",
    "plt.legend(['Politician', 'Artist', 'Company', 'Public Figure'])\n",
    "plt.xlabel('Degree')\n",
    "plt.ylabel('Number of nodes')\n",
    "plt.title('Facebook Networks by Category')\n",
    "plt.savefig('fb_network_degree_distr.png')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# we can check assortativity\n",
    "print(\"Politician network assortativity: {}\".format(nx.degree_assortativity_coefficient(poli_net)))\n",
    "print(\"Artist network assortativity: {}\".format(nx.degree_assortativity_coefficient(art_net)))\n",
    "print(\"Company network assortativity: {}\".format(nx.degree_assortativity_coefficient(co_net)))\n",
    "print(\"Public figure network assortativity: {}\".format(nx.degree_assortativity_coefficient(pub_net)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# check clustering coefficient\n",
    "cc = nx.clustering(poli_net)\n",
    "avg_cc_poli = sum(cc.values()) / len(cc)\n",
    "print(\"Politician network clustering coefficient:\", avg_cc_poli)\n",
    "\n",
    "cc = nx.clustering(art_net)\n",
    "avg_cc_art = sum(cc.values()) / len(cc)\n",
    "print(\"Artist network clustering coefficient:\", avg_cc_art)\n",
    "\n",
    "cc = nx.clustering(co_net)\n",
    "avg_cc_co = sum(cc.values()) / len(cc)\n",
    "print(\"Company network clustering coefficient:\", avg_cc_co)\n",
    "\n",
    "cc = nx.clustering(pub_net)\n",
    "avg_cc_pub = sum(cc.values()) / len(cc)\n",
    "print(\"Public figure network clustering coefficient:\", avg_cc_pub)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### c. Visualize network\n",
    "\n",
    "**Homework:** Try out multiple visualizations, and decide which visualization method creates an informative plot for the network."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### d. Takeaways\n",
    "\n",
    "* politician network has highest clustering coefficient (CC = 0.39) -> political views tend to cluster people more densely\n",
    "* public figure network has the highest assortativity -> the only network that reflects human relationship type of connectivity\n",
    "* disassortativity seen only in artist networks may be indicative of competitiveness, desire not to like/promote other popular peers\n",
    "* lowest average degree found in company network\n",
    "* highest average degree seen in artist network\n",
    "* each network has similar degree distribution with heavy tail -> most nodes have small number of connections, while a few nodes (hubs) have significantly higher number of links\n",
    "* and many more insights with more detailed analyses -> it is your homework to explore more! :)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### V. 1. Social Networks - Physicians "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# load physicians network\n",
    "G_phys = nx.read_edgelist(\"../datafiles/social/physicians/out.moreno_innovation_innovation\", comments='%')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "len(G_phys.nodes)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "len(G_phys.edges)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.draw(G_phys, node_size=5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.is_connected(G_phys)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.number_connected_components(G_phys)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "cc = nx.clustering(G_phys)\n",
    "avg_cc_poli = sum(cc.values()) / len(cc)\n",
    "print(\"Physicians network clustering coefficient:\", avg_cc_poli)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "hist_pub = degree_distr(G_phys)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plt.figure()\n",
    "plt.loglog(hist_pub.T[0],hist_pub.T[1],'ro-')\n",
    "plt.legend(['Physicians'])\n",
    "plt.xlabel('Degree')\n",
    "plt.ylabel('Number of nodes')\n",
    "plt.title('Physicians')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "ba = nx.barabasi_albert_graph(100, 3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nv.ArcPlot(G_phys).draw()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nv.CircosPlot(ba).draw()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We practiced and tried out different analysis techniques using social network data as case-study. \n",
    "\n",
    "**Homework:** below you can explore the infrastructure, technological, biological, lexical networks and analyze their properties on your own! "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### V. 2. Infrastructure Networks"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "G_infra = nx.read_edgelist(\"../datafiles/infrastructure/powergrid/out.opsahl-powergrid\", comments='%')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### V. 3. Technological Networks"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "G_tech = nx.read_edgelist(\"../datafiles/technological/p2p/p2p-Gnutella08.txt\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### V. 4. Biological Networks"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "G_bio = nx.read_edgelist(\"../datafiles/biological/protein/out.moreno_propro_propro\", comments='%')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### V. 5. Lexical Networks\n",
    "\n",
    "How to import node attributes located in a separate file."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "G_lex = nx.read_edgelist(\"../datafiles/lexical/david_copperfield/out.adjnoun_adjacency_adjacency\", comments='%')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nodes are listed as numbers, but when visualizing our network, we would like to see the words that represent those nodes. The words are stored in a separate file, in `ent.adjnoun_adjacency_adjacency.word.name`, and the index of the word corresponds to the index of the node. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# load node name data for each node in the network\n",
    "with open(\"../datafiles/lexical/david_copperfield/ent.adjnoun_adjacency_adjacency.word.name\") as file:\n",
    "    node_name = {}\n",
    "    i = 1 \n",
    "    for line in file:\n",
    "        node_name[str(i)] = line.strip()\n",
    "        i += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# assign the name of the node to the node in the graph\n",
    "nx.set_node_attributes(G_lex, node_name, 'name')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.get_node_attributes(G_lex, 'name')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.draw(G_lex, labels=node_name, node_color='y')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## VI. Bonus: Network Features for Machine Learning Models\n",
    "\n",
    "Network features can be incorporated in machine learning algorithms to improve prediction capabilities. The network structural properties that provide unique features on the node, such as node degree, node centrality, node clustering coefficient, etc. Network topological measures provide additional information that are connectivity dependent, which are additional features for prediction.\n",
    "\n",
    "We can also use the network structure to calculate new features based on the neighborhood of each node, such as the average degree of the nearest neighbors, the median neighbor strength, etc."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
